/*
https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/solution/yu-shu-zu-zhong-yuan-su-de-zui-da-yi-huo-7erc/
 */
import java.util.Arrays;

public class Solution1707 {

    static class Trie{
        Trie[] children=new Trie[2];
        int min=Integer.MAX_VALUE;

        void insert(int t){
            Trie node=this;
            node.min=Math.min(node.min,t);
            for (int i=29;i>=0;i--){
                int bit=(t>>i)&1;
                if (node.children[bit]==null){
                    node.children[bit]=new Trie();
                }
                node=node.children[bit];
                node.min=Math.min(node.min,t);
            }
        }

        int get(int t,int limit){
            Trie node=this;
            if (limit<node.min){
                return -1;
            }
            int ans=0;
            for (int i=29;i>=0;i--){
                int bit=(t>>i)&1;
                if (node.children[bit^1]!=null && node.children[bit^1].min<=limit){
                    ans=ans|(1<<i);
                    bit=bit^1;
                }
                node=node.children[bit];
            }
            return ans;
        }
    }

    public int[] maximizeXor(int[] nums, int[][] queries) {
        Trie trie=new Trie();
        for (int num : nums) {
            trie.insert(num);
        }
        int[] ans=new int[queries.length];
        for (int i=0;i<queries.length;i++){
            ans[i]=trie.get(queries[i][0],queries[i][1]);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution1707().maximizeXor(new int[]{0,1,2,3,4},new int[][]{{3,1},{1,3},{5,6}})));
    }
}
